package leetcode_core.leetcode_7;

import java.util.*;

/**
 * 课程表
 *
 * @author: 张庭杰
 * @date: 2023年02月25日 15:28
 */
public class CanFinishBFS {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //1. 广度优先搜索
        int[] inDegree = new int[numCourses];
        int[] ans = new int[numCourses];
        List<Integer>[] graph = buildGraph(numCourses, prerequisites, inDegree);
        //2. 首先先找到那些入度为0的节点,作为初始化的节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0;i<numCourses;i++) {
            if(inDegree[i] == 0){
                q.offer(i);
            }
        }
        //3. 开始搜素
        int count = 0;
        while(!q.isEmpty()){
            Integer head = q.poll();
            ans[count++] = head;
            //3.1 抹去当前当前所有有相连的节点的连线
            for (Integer to : graph[head]) {
                if(--inDegree[to] == 0){
                    q.offer(to);
                }
            }
        }
        if(count == numCourses){
            return ans;
        }
        return new int[]{};
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites,int[] inDegree){
        // 1. 创建图
        List<Integer>[] graph = new LinkedList[numCourses];
        //2. 扫描当前选课的情况
        for (int[] prerequisite : prerequisites) {
            int from = prerequisite[1];
            int to = prerequisite[0];
            inDegree[to]++;
            graph[from].add(to);
        }
        return graph;
    }

}
